package com.linkedlist;


/**
 * @author 江岸
 * @version V1.0
 * @ClassName: Josepfu
 * @description: 约瑟夫问题
 * @date 2020/12/118:58
 * @since V1.0
 */
public class Josepfu {

    public static void main(String[] args) {
        CircleSingleLinkedList circle = new CircleSingleLinkedList();
        circle.addBoy(5);
        //circle.show();
        circle.countBoy(1,2,5);
    }


}
//构建环形单项链表
class CircleSingleLinkedList{
    //创建一个first节点
    private Boy first = null;
    //添加小孩的方法，构建成一个环形的链表
    public void addBoy(int nums){
        if(nums<1){
            System.err.println("输入的数字不符合规则");
            return;
        }
        Boy cur = null;
        for (int i=1;i<=nums;i++){
            if (i==1){
                first  = new Boy(1);
                first.setNext(first);
                cur = first;
            }else {
                cur.setNext(new Boy(i));
                cur = cur.getNext();
                cur.setNext(first);
            }
        }
    }

    //遍历
    public void show (){
        if (first==null){
            System.out.println("没有任何小孩");
            return;
        }
        Boy cur = first;
        while (true){
            System.out.printf("小孩的编号%d \n",cur.getNo());
            cur = cur.getNext();
            if (cur == first){
                break;
            }
        }
    }

    //根据用户的输入，计算出小孩出圈的顺序
    /*
     * @Param: [startNo, countNum, nums]
     * 起始位置，数几下，初始小孩数
     */
    public void countBoy(int startNo,int countNum,int nums){
        if (first ==null||startNo<0||startNo>nums){
            System.err.println("输入的参数有误");
            return;
        }
        //先把first指针移动到第一个小孩
        while (true){
            if (first.getNo() == startNo){
                break;
            }
            first = first.getNext();
        }
        //helper指针指向最后一个小孩
        Boy helper = first;
        for (int i=1;i<nums;i++){
            helper = helper.getNext();
        }
//        System.out.println(first.getNo()+","+helper.getNo());
        //开始报数，出圈
        while (true){
            if (first==helper){
                System.out.println("最后的小孩编号:"+first.getNo());
                break;
            }
            for (int i=1;i<countNum;i++){
                first = first.getNext();
                helper = helper.getNext();
            }
            System.out.println(first.getNo());
            first = first.getNext();
            helper.setNext(first);
        }
    }

}

//boy节点
class Boy{
    private Integer no;//编号
    private Boy next;//指向下一个节点

    public Boy(int no) {
        this.no = no;
    }

    public Integer getNo() {
        return no;
    }

    public void setNo(Integer no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}